#include <bits/stdc++.h>
using namespace std;

/*
2843. 统计对称整数的数目
已解答
简单
相关标签
相关企业
提示
给你两个正整数 low 和 high 。

对于一个由 2 * n 位数字组成的整数 x ，如果其前 n 位数字之和与后 n 位数字之和相等，则认为这个数字是一个对称整数。

返回在 [low, high] 范围内的 对称整数的数目 。

 

示例 1：

输入：low = 1, high = 100
输出：9
解释：在 1 到 100 范围内共有 9 个对称整数：11、22、33、44、55、66、77、88 和 99 。
示例 2：

输入：low = 1200, high = 1230
输出：4
解释：在 1200 到 1230 范围内共有 4 个对称整数：1203、1212、1221 和 1230 。
 

提示：

1 <= low <= high <= 104
*/

// 法一
class Solution {
	public:
	int countSymmetricIntegers(int low, int high) {
		int count = 0;
		
		// 处理两位数（2n位，n=1）
		if (low <= 99) {
			int lower = max(low, 10);
			int upper = min(high, 99);
			if (lower <= upper) {
				int first = ((lower + 10) / 11) * 11; // 第一个>=lower的11倍数
				if (first < lower) first += 11;
				if (first <= upper) {
					int last = (upper / 11) * 11;
					count += (last - first) / 11 + 1;
				}
			}
		}
		
		// 处理四位数（2n位，n=2）
		if (high >= 1000) {
			int start = max(low, 1000);
			int end = min(high, 9999);
			
			for (int s = 1; s <= 18; ++s) { // 前两位和后两位的和范围1~18
				int a_min = max(1, s - 9);   // 前两位千位a的最小值
				int a_max = min(9, s);        // 前两位千位a的最大值
				int pre_count = a_max - a_min + 1;
				if (pre_count <= 0) continue;
				
				int post_count = (s <= 9) ? (s + 1) : (19 - s); // 后两位的组合数
				if (post_count <= 0) continue;
				
				for (int a = a_min; a <= a_max; ++a) {
					int b = s - a;
					int ab = a * 10 + b; // 前两位组成的数（如a=1,b=2则12）
					
					for (int c = 0; c <= min(s, 9); ++c) { // 后两位十位c的可能值
						int d = s - c;
						if (d < 0 || d > 9) continue;
						int num = ab * 100 + c * 10 + d;
						if (num >= start && num <= end) {
							count++;
						}
					}
				}
			}
		}
		
		return count;
	}
};

// 法二
class Solution {
	public:
	int countSymmetricIntegers(int low, int high) {
		int count = 0;
		for (int num = low; num <= high; ++num) {
			string s = to_string(num);
			int len = s.length();
			if (len % 2 != 0) {
				continue;
			}
			int n = len / 2;
			int sum1 = 0, sum2 = 0;
			for (int i = 0; i < n; ++i) {
				sum1 += s[i] - '0';
			}
			for (int i = n; i < len; ++i) {
				sum2 += s[i] - '0';
			}
			if (sum1 == sum2) {
				++count;
			}
		}
		return count;
	}
};